package pro.softzhang.algo.lc200;

import pro.softzhang.algo.common.ListNode;

/**
 * TODO 加练
 */
public class LC234_PalindromeLinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1, null))));
        boolean isPalindrome = new Solution().isPalindrome(head);
        System.out.println(isPalindrome);
    }

    static
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) {
                return true;
            }

            ListNode slow = head, fast = head.next;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            ListNode secondPart = slow.next;
            // 留出中间节点
            if(fast.next != null) {
                secondPart = slow.next.next;
            }
            slow.next = null;

            return equals(head, reverse(secondPart));
        }

        public ListNode reverse(ListNode head) {
            ListNode previous = null, current = head;
            while (current != null) {
                ListNode next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }
            return previous;
        }

        public boolean equals(ListNode head1, ListNode head2) {
            while (head1 != null && head2 != null) {
                if(head1.val != head2.val) {
                    return false;
                }
                head1 = head1.next;
                head2 = head2.next;
            }
            return head1 == null && head2 == null;
        }
    }
}